package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-28 18:09
 */
public class QuickSort03<E>  extends Sort<E> {

    @Override
    protected void sort() {

        sort(0,elements.length);
    }

    private void sort(int begin,int end) {

        E base = elements[begin];

        int left = begin + 1, right = end - 1;

        while (left <= right) {

            // 找到小于或者等于base的值
            while (left <= right && compare(base,elements[right]) < 0) {

                right--;
            }

            // 找到大于或者等于base的值
            while (left <= right && compare(base,elements[left]) > 0) {

                left++;
            }

            if (left>= right) {

                break;
            }

            swap(left,right);
            if (compare(left,right) == 0) {

                left++;
                right--;
            }
        }

        swap(begin,right);

        if (right > begin + 1) {

            sort(begin,right);
        }

        if (right + 1 < end) {

            sort(right + 1, end);
        }
    }
}
